perm filename SYS2[NUM,DBL] blob
sn#147283 filedate 1975-02-25 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00042 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00005 00002 .DEVICE XGP
C00007 00003 .PORTION TITLEPAGE
C00008 00004 2CONTENTS*
C00009 00005 2↓_SUMMARY_↓*
C00013 00006 21. INTERNAL ACTIVITY*
C00027 00007 22. INITIAL KNOWLEDGE*
C00031 00008 5Level 1*
C00036 00009 5Level 2*
C00037 00010 Specific Knowledge
C00042 00011 Strategies
C00047 00012 Meta-strategies
C00049 00013 5Level 2B: example starting domains*
C00055 00014 5Level 2C: Tentative organization*
C00067 00015 5Level 3*
C00068 00016 Specific Knowledge
C00069 00017 Set Theory
C00083 00018 Deduction -- much of this goes under problems-to-prove strategies
C00092 00019 Induction -- much is also relevant to prob-to-prove and prob-to-find strategies
C00099 00020 Operation
C00110 00021 Structure
C00113 00022 Conservation
C00115 00023 Control
C00116 00024 Handles (how it can be accessed)
C00117 00025 Strategies 6(for each, supply hints as to how to pick likely candidates, in case no other good reason is known)*
C00118 00026 General
C00124 00027 When examining any new entity (operator, object, construct, concept)
C00128 00028 When examining a new operation "f"
C00132 00029 When examining a non-procedural object (set, class, concept)
C00133 00030 When examining a semi-procedural problem to prove (theorem, conjecture)
C00136 00031 When examining a semi-procedural problem to find
C00138 00032 Meta-strategies
C00142 00033 Meta-meta-strategies
C00144 00034 Meta-meta-meta-strategies
C00145 00035 Meta-meta-meta-meta-strategies
C00146 00036 23. REPRESENTATION*
C00147 00037 5Level 2*
C00153 00038 24. COMMUNICATION*
C00158 00039 25.EXAMPLES*
C00159 00040 5Example 1: Contemplation forming links, intuitive conjectures*
C00167 00041 5Example 2: Discovering and developing a family of analogies*
C00172 00042 5Example 3: Formally Investigating an intuitively believed conjecture*
C00176 ENDMK
C⊗;
.DEVICE XGP
.!XGPCOMMANDS←"/TMAR=50/PMAR=2100/BMAR=50"
.FONT 1 "BASL30"
.FONT 2 "SIGN57"
.FONT 3 "SHD40"
.FONT 4 "BASI30"
.FONT 5 "BASB30"
.FONT 6 "NGR25"
.FONT 7 "NGR20"
.FONT 8 "GRFX35"
.TURN ON "↑↓_π{"
.TURN ON "⊗" FOR "%"
.PAGE FRAME 47 HIGH 89 WIDE
.AREA TEXT LINES 4 TO 45
.AREA HEADING LINES 1 TO 3
.AREA FOOTING LINE 48
.!XGPLFTMAR←120
.SPACING 50 MILLS
.PREFACE 150 MILLS
.NOFILL
.PAGE FRAME 47 HIGH 89 WIDE
.AREA TEXT LINES 4 TO 45
.AREA HEADING LINES 1 TO 3
.AREA FOOTING LINE 47
.PREFACE 35 MILLS
.FILL
.COUNT PAGE PRINTING "1"
.NEXT PAGE
.PAGE←0
.MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
.MACRO E ⊂ APART END ⊃
.TABBREAK
.EVERY FOOTING(,⊗7Last edited 1/20/75⊗*,)
.PORTION TITLEPAGE
.BEGIN CENTER RETAIN
⊗2THEORY FORMATION:⊗*
⊗6Some Initial Thoughts on⊗*
⊗2A SYSTEM WHICH CAN
DEVELOP MATHEMATICAL
CONCEPTS INTUITIVELY⊗*
.END
.GROUP SKIP 10
.NOFILL
⊗3DOUG LENAT
AVRA COHN
STANFORD UNIVERSITY
ARTIFICIAL INTELLIGENCE LABORATORY
⊗*
SECOND SKETCH
⊗4Not for distribution⊗*
.NEXT PAGE
.ONCE CENTER
⊗2CONTENTS⊗*
.GROUP SKIP 10
.BEGIN NOFILL PREFACE 150 MILLS
0. Summary
1. Internal Structure and Activity
2. Initial Knowledge in the system
3. Representation of this knowledge
4. Communication with the user
5. A few examples
.END
.FILL
.EVERY HEADING(⊗3MATH THEORY FORMATION⊗*,,⊗4Doug Lenat and Avra Cohn⊗*)
.EVERY FOOTING(⊗71/20/75,,page SYS2 . {PAGE})
.NEXT PAGE
.ONCE CENTER
⊗2↓_SUMMARY_↓⊗*
.GROUP SKIP 5
The methods of mathematical creativity are being studied. More than
merely a taxonomy of theory formation, this project is the foundation for a
system which will learn -- and do -- mathematics. Initially, this system will
possess some general strategies and some powerful but opaque "intuitive" ability
(e.g., the ability to simulate physical experiments and perceive the results).
A ⊗4contemplative⊗* period will allow the system to develop concrete facts about its
world and specific techniques (by combining general strategies with observations).
The system would also combine its intuitions to form plausible "theorems"; when
definitions are later provided formally, these will be proposed, and the intuitive
justification will already be present.
The activities in this period are
expected to be universal, not limited to any single
domain of mathematics.
After a while, the system will request inputs from
a human user, in what is to be an ⊗4assimilative⊗* phase.
These teachings should be the
core definitions of a specific field, and of course should be based on what is
already mastered. The first experiences could be in set theory, Boolean algebra,
abstract algebra, logic, or
arithmetic.
Finally, the ⊗4investigative⊗* mode would prevail. In conjunction with a
human adviser, the system would propose and explore interesting new relationships,
decide which creations to name, explore the intuitive meanings of statements, etc.
The driving and pruning forces in all phases are aesthetics and utility.
The central mechanisms are
families of BEINGs which live and work in a powerful control environment.
.BEGIN SELECT 6 SPACING 20 MILLS PREFACE 100 MILLS SKIP 3
BEINGs are uniformly structured knowledge modules. (see Green et al.,
⊗4Progress Report on Program-Understanding Systems⊗*, Memo AIM-240,
CS Report STAN-CS-74-444, Artificial Intelligence Laboratory, Stanford
University, August, 1974; or see Lenat, D., ⊗4BEINGS: Knowledge as
Interacting Experts⊗*, forthcoming.)
They are similar to ACTORs, except that BEINGs have structure. Each BEING
in a family has the same set of parts; all parts with the same name have the same
structure (format). This preserves some advantages of both uniformity
and structure.
.END
.NEXT PAGE
.ONCE CENTER
⊗21. INTERNAL ACTIVITY⊗*
This quite tentative description is meant to get things off the ground.
As more demands are imposed, it may well crumble, hopefully to reveal a better
internal organization.
There are seven types of BEINGs:
.B
Object type of Specific Knowledge
Operator type of Specific Knowledge
Conjecture type of Specific Knowledge
Strategy
Meta-Strategy
Meta-meta-strategy
Meta-meta-meta-strategy
.E
Each type has its own set of parts (although there will be many parts present in
many types, e.g. NAME). For each type t there will be an archtypical BEING
B↓t. Under each part of B↓t will be a partially ordered set of strategies
for dealing with that part of that type of BEING (how to fill it out, how to
extend it, what its structure is). Notice we are saying that all the parts with
the same name, of BEINGs of the same type, will all have the same structure.
This is one additional level of structure from the BEINGs proposed in PUP6.
The strategies are all organized under specific parts of archtypical BEINGs.
That is, a strategy is pointed to by what part of what BEING type it is related
to filling out. The strategies are (partially) ordered in each such clump. When
a meta-strategy decides that part p of BEING B is to be filled out, the type of
B is looked up. Say it is t. Then the sequence of strategies listed under part p
of B↓t is executed. This set is pointed to by part p of B.
When part p of BEING B is filled out, at some point in the sequence S of strategies
listed under part p of the archtypical BEING with same type as B, some new
information may be discovered. If S cannot handle this knowledge, then it will
simply return with the message "I am not through, but here is some fact(s) which
may mean that filling out p is no longer the best activity".
The meta-stragegies are organized in groups or clumps. When such an interruption
is reported, the clump of MS (meta-straegies) which receives it first decides
whether or not it is still the best clump to be in control. If not, it relinquishes
control to the clump of MMS which called it, etc. If it is stillthe relevant
clump, the MS again evaluate themselves to see what part of what BEING should
be filled in now. It may turn out to be p again, or it may change due to the new
info which p supplied. (To make this choice faster, each MS recalls the args and
the final computed value the last time it was called on; if nothing has
changed for it, then it need not recompute its value.) When p returned its
interruption message, it replaced its pointer (formerly to the first
strategy on B↓t, part p) by a pointer to the strategy where it left off work.
Whenever part p of BEING B gets chosen again (which is often immediately), it
will resume just where it stopped work earlier.
The flavor of the return should thus be one of: Not Done because x is
possibly more interesting; Not Done because x is a prerequisite to doing me;
Done because I succeeded; Done because I failed utterly.
In addition to the seven types of BEINGs, the control structure of the system
will embody knowledge of communication (both internally and with the user),
meta↑4stratgies or higher level concerns, global level strategies (choice),
and the basic control algorithm of the system.
The lower-level BEINGs will provide fast access to well-organized information.
The meta-strategy BEINGs will have few parts, hence be sufficently
fast. Higher level-BEINGs will be so rarely called upon that their slowness
is immaterial, thus the intelligent-but-slow character of highly structured
BEINGs is acceptable.
Notice once more the structure: seven types of BEINGs; each type breaks into
several clumps. Each BEING of each type has the same set of parts. Each clump
of BEINGs has members for determining if that clump is still the relevant one.
Each part of a given type of BEING has a distinctive structure, shared by all
parts with the same name, in all BEINGs of the same type. Each type of BEING
has an archtypical representative; the values of its parts specify the structure
formats mentioned in the previous sentence. All archtypical BEINGs' parts have
a single universal format for specifying this information.
The control is thus very traditional: at each instant, one strategy of each
level will be activated; when it returns to a higher level, ⊗4that⊗* level's
strategies must decide whether their little clump is still relevant. THe
relevant clump at that level then chooses a new one at a lower level.
The role of strategies of level x is thus seen to be one of choosing not
the strategy of level x-1 to employ, but rather which clump of meta↑x↑-↑1
strategies are relevant.
Each clump is (at least partially) ordered, hence can be executed sequentailly.
The result may be to choose a lower-level clump, and/or modify some strategies
at some level (some part of some BEING), and/or create new strategies at some
level (perhaps even to create a new BEING).
The next step is to list the parts of each of the seven types of BEINGs,
followed by filling these in with general strategies for how to fill in such
parts of such BEINGs. Next, all the specific knowledge must be rephrased in
terms of specific knowledge BEINGs. All the hig level meta-strategies must
be similarly phrased. In doing all this, representation decisions must be
made (e.g., when talking specificly about the INTUITION part, one must know
what formats to expect there). The clumpings at each level (esp. MS) must be
made, and special knowledge added to decide when the current clump is no longer
the one which should be in control.
At this stage, the system will be ready for hand simulation and then coding.
Extra internal ideas which were rejected from the third sketch of the system:
To each part corresponds an archetypical BEING,
giving information about any part having
that name (how to fill it in, when to extend it, etc.) One part of each
archetypical BEING is called Representation, and describes the format in which each
BEING must keep info. stored inside that part.
The typical flow of control would follow these patterns:
.B
Decisions
A. Choose relevant family of BEINGs
B. Choose relevant subfamily of BEINGs
C. Choose relevant group of parts
D. Choose specific relevant BEING
E. Choose specific relevant part
F. Work on that part of that BEING
If its REPR. is that of several alternative BEINGs, then recurse to step D
Constraints
A will generally precede all others
B will generally precede D
C will generally precede E
F will generally succeed all others
.E
The environment selects a group of BEINGs, who then fight among themselves
(their RECOG group of parts) to determine exactly who the winner is. If the
winner is himself a node representing a group of BEINGs, that group must also
compete among itself for control, etc. Similarly for deciding which part of the
BEING is relevant. If the rele. part of the rele. BEING is itself a pointer to
a group of BEINGs, then the process recurs (except that the same part of the
new winner is probably wanted). The environment does not make the decisions; it
⊗4does⊗* do two things related to this, though: it decides which of A,B,C,D,E,F
is to be settled next, and then it chooses the entity who
will get to make that selection. The first job is simplified since there are
only six legal orders:
.B
ABCDEF
ABCEDF
ABDCEF
ABDCEF
ACBDEF
ACBEDF
ACEBDF
.E
An exception would be when a specific BEING is known to be wanted; then
A, B, and D are made simultaneously.
.SELECT 6
One difference from PUP6 is that here the BEINGs are grouped into families.
Each type has its own set of parts (although there will be many parts present in
many types, e.g. NAME). For each type t there will be an archetypical BEING
B↓t. Under each part of B↓t will be a partially ordered set of strategies
for dealing with that part of that type of BEING (how to fill it out, how to
extend it, what its structure is). Notice we are saying that all the parts with
the same name, of BEINGs of the same type, will all have the same structure.
This is one additional level of structure from the BEINGs proposed in PUP6.
.SELECT 1
The strategies are all organized under specific parts of archetypical BEINGs.
That is, a strategy is pointed to by what part of what BEING type it is related
to filling out. The strategies are (partially) ordered in each such clump. When
the relevant object is part p of BEING B, the type (family name) of
B, say it is t, knows what parts B has.
Then the sequence of strategies listed under part p
of B↓t is executed. This set is pointed to by part p of B.
.NEXT PAGE
⊗22. INITIAL KNOWLEDGE⊗*
This section proposes a corpus of information, some of which will be carefully
constructed, and all of which should
be present in the system before the user approaches it.
This presentation will be repeated at several levels of detail, so that
the reader will obtain a global view before going into detail.
The deeper the level, the more definite the assumptions which are needed in
order to fill out the knowledge. Even at the descriptive level in this
document, some representation decisions had to be tentatively assumed.
There are two distinct hierarchies or levels of knowledge. The one
which dominates this organization is meta↑*strategies, where meta↑-↑1strategies
are just specific facts, meta↑0strategies are strategies, etc. Each level
contains rules and hints for handling the entities one level lower. The
second kind of hierarchy exists at one level, dealing with objects of more
and more generality. For example, "tie new concept in to existing ones" is
at the same level yet subsumes "consider composition of f and existing fns."
Thus there is some grammar, some generation scheme,
whereby general strategies (at a given level) combine with specific facts
or with other strategies (at any level) to produce tailored, specialized
strategies at that level (more concrete but less generally applicable).
Perhaps thee should be four distinct stages of operation of the system.
First comes a strategy-development phase, where all these special strategies
are grown.
Next comes a trial exploration phase, where interrelationships
and facts ⊗4independent of any particular mathematical domain⊗*,
or intuitive
relations which may be domain-specific, are developed. The system
will finally be ready to confront the user, who feeds in specific facts,
definitions, conventions, and suggestions about a particular domain.
The fourth stage then begins, with the actual user-system dialogue on a
particular branch of mathematics.
⊗5Level 1⊗*
.NOFILL
Specific Information: Facts, Objects, Operations, spanning several domains.
Strategies for effective use of this information, of knowledge in general.
Meta-strategies, which help in the selection of efficacious strategies.
Meta-meta-strategies, which help select relevant meta-strategies.
Meta-meta-meta-strategies, which help define the system's values.
Meta-meta-meta-meta strategy: maximize net worth of behaviors
⊗5BEINGs present initially⊗*
The following is a sketch of how the top few levels of knowledge in the system
are organized. Each node in the right lower section is both a BEING and the
archetyical representative of a group of BEINGs. The parts of the BEINGs are also
each represented by BEINGs in the system, though not in the picture below.
.BEGIN SELECT 8 NOFILL PREFACE 0 MILLS TURN OFF "↑↓"
.GROUP
Knowledge
~
⊂ααααααααααααααααααααααααααααβααααααααααααααααααααααααααααααα⊃
↓ ↓ ↓
Environment Meta Specific
~ ~ ~
~ ⊂ααααα∀ααααα⊃ ⊂αααααααα παααααα∀ααααααα⊃
↓ ↓ ↓ ↓ ↓ ↓
Control Active Static Parts Relation Object
~ ~ ~ ~ ~
⊂ααααααααπααααααααααπααααααααλ ~ ↓ ↓ ↓
↓ ↓ ↓ ↓ ~ Recog Order (Tree)
Assume Guess Test Communicate ~ Alter = Set
⊂ααααααπααααααααπααααααααπααααπααααααααααλ Act ⊗6ε⊗* Bag
↓ ↓ ↓ ↓ ↓ ↓ Info ⊗1⊂⊗* List
Counterex. Msg. Assumption Pf. Thm. Conjecture ∨,∧ Axioms
@,⊗6↔⊗* (a,b)
⊗6¬⊗* Hist
⊗1∪,∩⊗* Oset
.APART
⊗1This could be carried on further beneath each node. For example, under "proof":⊗*
.GROUP
Proof
~
⊂αααααααααααααααααααααα∀αααααααααααα⊃
↓ ↓
Universal Existential
~ ~
⊂αααα∀αααα⊃ ⊂αααααααααααααααα∀ααααααααα⊃
↓ ↓ ↓ ↓
Direct Indirect Direct Indirect
~ ~
⊂αααααααααααα∀ααααααα⊃ ⊂αααααααααα∀αααααααααα⊃
↓ ↓ ↓ ↓
Constructive Deductive Constructive Deductive
.E
In most cases, however, the subsidiary information should be simple BEING parts, not
new BEINGs. For this reason we terminate our graph at this level.
⊗5Level 2⊗*
.TURN OFF "{}"
Specific Knowledge
Set Theory
set
membership, ⊗6ε⊗*, non-membership
containment, ⊂, ⊃, subset, superset, incomparability
equality, =, ≠, inequality
intersection, ∩
union, ∪
complement, ', difference, -
disjoint
partition
null set, NIL, ⊗4phi⊗*, {}, emptiness
singleton set, {{}}, (NIL), non-emptiness
doubleton, pair, non-identity of elements, ordered pair
bigger-than-doubleton, more-than-two, several
universal set, universe
infinity, finite, ∞
Deduction
Truth, falsity, certainty
Definition, axiom, theorem, lemma
Proof, validity, unsatisfiability
and, conjunction, ∧
or, disjunction, ⊗6∨⊗*
not, negation, ¬
variable, constant
substitution, replacement
quantification, for all, ∀, existence, ∃, ¬∀, ¬∃
implication, →, ¬→, equivalence, ↔, if, iff, only if
scope, binding, free
mathematical induction, recursion, well-ordering axiom
rules of deductive inference, modus ponens and tollins
contradiction, reductio ad absurdum
cases
Induction
plausibility, certainty, belief, betting, reliability
conjecture, hypothesis, intuit, guess, assumption
probability routines for handling derived statements
empiricism, experiment, random sampling, statistics
what it means to be a generalization, a specialization
what it means to be an analogy, a model
Operation
Relation
function
domain, range, image
inverse, preimage
onto, surjection
1-1, injection
1-1 correspondence, bijection
composition, associativity
uniqueness
extension, restriction
fixed point
identity function
repeated application of a function
symmetry, reflexivity, transitiviy, equivalence, partition
pairing
Procedure, sequence, seriation, program
Parallel, simultaneous
Ordering, partial and total, ≤, ≥, <, >, =, trichotomy
Structure
tree, binary tree
tuple (associativity of functions), list, vector
bag (commutativity and associativity)
set, class, collection
trivial cases of each structure
regularity, order, form, arrangement
Conservation
of inertia; frame problem
invariance
(in)elasticity, fluidity, rigidity, plasticity
Control
what a strategy means, what a meta*-strategy means
choice, decision
goal, object, end, purpose
problem, solution, search, task
Handles (how it can be accessed)
existence can be proven
constructive proof
efficient algorithm for construction
built into the language, pointer
Strategies
General
Analogy: find regularity among concepts
Find regularity within this concept itself (recurrence, pattern)
Contradiction: what it means, how to resolve it
Choice: algorithms, hints for selection, decision-making
Assimilation: identify, tie-in, grasp intuitively
Find the worth (promise) of this concept, of some special parts
When examining any new entity (operator, object, construct, concept)
Identify: get names
Boundary: get limits of this concept/definition
Extension/restriction: how can this boundary be changed (incr. interest)
Handle: get the most concrete, efficient handle possible on this
Character: what class does this entity fall into?
Combination: how can this be combined with similar entities
Tie-in: relationship to similar entities which exist already
Examples: simple, sophistocated, boundary, typical, near miss
When examining a new operation "f"
Definite: get names for function, its domain and range
Calculation: get algorithm for computing f
Character: see if it is a function or only a relation
Image: what subset of range R does the domain D map onto
Extension: can D be extended so f is ONTO R, or onto Q⊃R
Restriction: can R be restricted so f is ONTO R
can D be restricted so f is 1-1 into R
Closure: can D be made to contain R or R↑2 or R↑3 or...
What to do if closure holds
Composition with existing functions and relations
Similarity: how to find it, what to do once it's found
Examples: Find some examples of this operation
Intuit: Try to construct an intuitive representation for f.
Identify: Initialize a list of ways that f might be referred to
When examining a non-procedural object (set, class, concept)
Containment: intersting subsets and supersets
Identity: name, interesting properties, distinguishing features
Operations: what can/can't be done to it, why, how to alter this
Is this the natural dom/range for any operators?
When examining a semi-procedural problem to prove (theorem, conjecture)
Intuitive: justification as well as assimilation
Tie-in: any entailment, causality, equivalent restatements
any with the same subject matter (or v. similar)
Boundary: what are the most likely counter-examples (and patches)
When examining a semi-procedural problem to find
Identify the parts: given (fixed, known) and unknown (goal)
Evalutate why this is interesting, difficult yet doable, usable later
Pull out the relevant facts
Analogy: can use results and/or methods from sim. tasks
Unify the intuitive and formal reprs. contributions
What is the idea/form of the soln?
Meta-strategies
General rules relating the following to each other:
completness of analogy,
using ana. for prediction,
interest in a B.,(⊗4B.⊗* stands for a concept, a unit of knowledge)
intutive nature of B.,
certainty, safety of a B.,
similar qualities of ⊗4parts⊗* of a B.
Also included here should be algorithms for applying these rules
to choosing the best strategies, as a function of the situation.
Meta-meta-strategies
Competing goals: maximize certainty, maximize interest
Heavily used → make efficient; already effic. → prefer to use this B.
Purely formal belief is dangerous but often leads to interesting results
Resolve choices in favor of aesthetic superiority
Also included here should be specific algorithms for applying these
rules to choosing the relevant meta-strategies.
Meta-meta-meta-strategies
Maximize desired effects
Minimize costs, conserve resources
Meta-meta-meta-meta-strategies
Eternal and implicit: maximize net behavior
.SKIP TO COLUMN 1
⊗5Level 2B: example starting domains⊗*
.FILL
Let us digress slightly, to show (at this level of detail) what the user
would have to input initially, to get started.
The first three examples below
are some of the places that seem most plausible to begin at; they are not
exhaustive, however.
The fourth example shows how the same system might be applicable, with no
change whatsoever, to handling theory formation in a domain which is not
generally thought of as part of mathematics: games of strategy.
In each case, the user must provide a definite form (e.g., definition),
an intuitive form (e.g., an archtypical diagram), and examples of each
object and each operator that is to be considered primitive in that
domain.
.NOFILL
Example 1: Theorem-Proving
Objects: axioms, parts of proofs
Operators: rules of inference
Miscellaneous: Hints about tying these in to pre-existing concepts.
Families of related proofs.
.BEGIN FILL
Once the system is "primed," the human repeatedly injects a proposed
theorem (or the system proposes one), and then the system tries to
intuitively understand (pictorially assimilate) and to formally
establish the theorem, or to find a counterexample. Notice that this
activity is not widely accepted as part of mathematics. If the
language is propositional calculus, then the system should indeed be
able to begin at this point. If the domain is predicate calculus, it
should be able to progress quickly to working on proofs, but this
would be "off the main track" of mathematics.
.END
Example 2: Set Theory
Objects: sets and their elements.
Distinguished: the empty set; singletons.
Operators: defining property of a set
how to construct new sets from old ones (∪,∩,',-,x)
membership, inclusion, incomparability, set equality
numerosity (compare two sets, see if ≤ or ≥)
Miscellaneous: View a relation as a subset of the cross-product of sets.
Restrict a relation to yield a function.
Restrict a function to yield a nicer function.
.BEGIN FILL
Once primed in this way, the user and/or system will propose new theorems,
definitions of new objects and operators, and so on.
.END
Example 3: Arithmetic
Objects: trees and their elements; special subclasses of tuples, bags, sets.
Operators: conversion of any tree/tuple/bag/set to canonical form which
preserves numerosity; successor; perhaps plus and/or times...
Miscellaneous: specific facts of set theory and logic, the relationship
(or a hint of it) between these theories and any arithmetic
operations which have been provided.
.BEGIN FILL
The user and system will propose new functions, and new theorems relating
them. To allow for their extension, new objects will be postulated.
.END
Example 4: Chess
Objects: pieces, spatial configurations of common combinations
Operators: moves, chunks of moves, rules of the game
Miscellaneous: openings; intuition about strategy and tactics.
.BEGIN FILL
Here the system would have no right to propose new objects or rules,
but it could (and should) propose treating an entire sequence of
moves as one new operator, devise overall strategy operators, etc.
The machine's game should improve with the play of several games, as
it develops the theory of chess.
.END
.NEXT PAGE
⊗5Level 2C: Tentative organization⊗*
Global concepts: these have analogues at every level of meta↑*strategy:
Rank all options, using current situation to determine priority weights
There should be a control character which is monitored as "user-interrupt"
Pick a meta↑4-strategy, use it to pick a meta↑3strategy, use them to pick
a meta↑2stragegy, use to pick meta-stragegy, use to pick strategies
A central theme is to achieve regularity via completion of the most interesting BEINGs
If you encounter x, or harder-than-x, when x is a current activity, bad news!
Information useful in filling out specific parts of BEINGs: these are really strategies
⊗7For a description of these parts, see Section 4: Representation. For a description of BEINGs, see paper by Green et.al. or by Lenat.⊗*
Definitions
Get the initial one from its genesis
Examine similar objects (esp. sim. defn), set up ana., see their alternate defns.
Often, define as similar object + some extra restriction/relaxation
Using intu., develop algorithm to find characteristic fn. for this B.
Get alg. for enumerating ⊗4all⊗*, then test with "⊗6ε⊗*" operator
Name
Find BEING generated analogously, find analogue of its chosen name
Ask the user, especially for variations, especially if user helped create it
Identification
Quick
If the name is explicitly mentioned
If the definition is matched perfectly
Standard
If description of when created, how, why, etc. match close enough
If it can do essentially what is wanted (better than all others)
Quick-NOT-
If some crucial "difference" is known to exist between this and similar BEINGS,
Then always check that this distinguishing feature is present first
NOT-
Examine similar BEINGs to ensure that this really is the closest one
Examples
Any kind
Quickest: specific specializations, exs. of genl. specializations
Consider ana. BEINGs' examples; examine their analogues
Consider intuitive grasp; convert directly to a few examples
Instantiate intuition with specific B.'s
Consider likely entities and test them to see if they qualify
Simple
Plug simple, distinguished concepts into the defin. or intuition
Consider the trivial case, base step, of recursive defn.
Sophistocated
Plug sophistocated concepts into the definition
If recursive, try to invert it for computational purposes
Find a family of simpler and simpler examples, then extrapolate
Rapidly scan entities until an unlikely example is found, then analyze it
Boundary
A boundar example is one which has some neighbors in, some not in, this concept
If two sim. entities are found, one in, other out, ∃ bdy. between them
Examine boundary very carefully to see exactly what causes it to be in/out
Typical (hard to characterize)
Not one of the other kinds
Plug in typical random values to defn.
Image
Intuitive
Set up ana, map intutive image across
Consider building up from intu. images of defn. objects and operators
Semi-concrete
More specific, computational, detailed; more costly to run, though
Ties to other BEINGs should be represented abstractly here
Internal representation: How exactly should this be stored
Ana.: similar as poss. yet efficacious representation part
Compatibility with reprs. this must interact with
Use some property of this concept to shortcut computation
Use some don't-care aspect: fix it so it adds to economy
Why
Point to difference w. other BEING if diff. is interesting
Point to what it can do (done to it) if that is interesting
Augment these with most of the WHY parts of sim. BEINGs
Usefulness
Use ana. BEINGs' USE part, actual records of their usage
What features of the diff. from sim B. makes this more(less) useful
When this is actually used, summarize its benefits here
Similar BEINGs
For each, find the difference description D.
To locate them, use intution, analogy, find one and use ⊗4its⊗* Similar part
Identify whether related by inclusion or not
Passive transformations
Find those operations which are applicable here; get general idea of this set
If only a few, see which are interesting by individual examination
If huge, try to restrict this class to known interesting ones
If huge, consider in reverse: what would be interesting result, then find ops.
What can almost (not quite be done)? If would be interesting, see why it fails.
Try to modify either this concept or interesting op. so it can be applied
Examine boundary examples, see if some operation can be used to push across bdy.
Active transformations
If this B. can DO something, what does it operate on (generalize from examples)
If it can't work on something, is this permanent or temporary?
Can it be altered slightly so as to be applicable to int. object
What are the results of this operation, the range, the values returned
Get these from gneralizing from examples
Similarly, what won't be returned, why not, how could this be changed to return it.
Evaluation vector
Aesthetic worth
a↓1e↑I
Bonus if some awkward B.s can now be simply expressed using this B.
Efficiency of handles
Global description of handle into 4 categories has biggest effect here
Run several trials and rate the results, to get finer values
Complexity
Roughly same as similar B.'s; use estimate of diff. as correction term
Average these estimates over several varied sim. Beings
Analogic utility
How detailed is the intutive image? the semi-concrete image?
Sum of interests of ana. applic. ops., / sim of actually appic. ops.
Definite utility
Overall value of the uses described in the USEFUL part
Update later as this BEING is used (or not used) not as expected
Generality
Number and variety of aux/subsidiary B.'s
⊗5Notes made on drafts of this sketch:⊗*
.FILL
Most mentioned metametastrategies are global and should be incorporated into the
interest-ascertaining algorithm. Abbreviations include β for BEING, π for part,
M for meta, S for strategy, sp. for specific, ob. object, op. operator, etc.
Those strategies which do not corr. to a βπ are typically control advisors, and
perhaps can be incorporated into the control structure opaque to the system.
For example: Contradiction is part of the belief mecahnaism, Choice is global
(perhaps made into a β), Assimilation is related to TIEIN π, Eval is related to
the VALUE parts and also the global evaluation mechanism.
.NOFILL
.SKIP TO COLUMN 1
⊗5Level 3⊗*
Originally, we felt that this level would bare the actual corpus of information
available to the system. It seems there must be yet another layer!
Specific Knowledge
Set Theory
set
intuitive representation as pointer structure
intuitive representation as rectangle in ⊗4Z⊗*↑2
intuitive representation of a set as a predicate
intuitive representation as analytic geom. equations
a set is completely determined by its members
operator: can take any elements and make them a set
operator: can add any elements to a set
membership, ⊗6ε⊗*, non-membership
how ⊗6ε⊗* is found using each representation of a set
how to make any object an element of a given set
how to make any object ¬⊗6ε⊗* of a given set
a set is interesting if its elements are related besides <sibling>
if two sets are different, then some member is only in one
if two sets are the same, then each member is in both
containment, ⊂, ⊃, subset, superset, incomparability
a set is determined by its subsets
a set is equal to its largest subset
the number of subsets of a set is much bigger than the set
the empty set is a subset of any set
each element of a set corresponds to the singleton subset containing it
if one set is a subset of another, it is smaller
if one is subset of other, all its elements are in the other
if all the elements of one are in the other, it is subset
to make a set a subset, all its elements must be added in
to make a set not a subset, only one element need be taken out
subset and superset are converse relations
examples of subsets, supersets, incomparable sets
equality, =, ≠, inequality
two sets are equal iff their elements coincide; i.e.,
two sets are equal iff each element of one is an element of the other
two sets are equal iff their subsets coincide; i.e.,
two sets are equal iff each subset of one is a subset of the other
two sets are equal iff each is a subset of the other
equality is reflexive
equality is symmetric
equality is transitive
inequality is the negation of equality, the complement
inequality is irreflexive
inequality is symmetric
if two sets are equal, one can be substituted for the other anywhere
there is a sentence which is false iff a set is replaced unequally
two sets are equal or unequal
an unequal subset is called a proper subset
two sets are incomparable or equal or properly related
intersection, ∩
the intersection of two sets is no bigger than the smallest
the ∩ of two sets equals one iff it is a subset of the other
the ∩ contains precisely those elements in both
the ∩ with an empty set is the empty set
the ∩ with a superset is the set
the ∩ with a subset is the subset
the ∩ of incomparable sets is a proper subset of each
if the ∩ is proper subset of each, they are incomparable
if the ∩ is not proper ⊂ one, that is a subset of the other
∩ can be repeatedly applied
∩ is associative
∩ is commutative
∩ of two equal sets is that set
∩ can be viewed as operating on a set of sets
compute: test each ele. of smaller set for ⊗6ε⊗* bigger set
union, ∪
∪ is as big as each set
∪ equals one set iff it contains the other one
∪ contains each set
∪ with an empty set is that set
∪ of incomparable sets properly contains each
∪ properly contain each means incomparable
∪ of two equal sets is that set
∪ is assoc.
∪ is commut.
∪ can work on a set of sets
how ∪ works on each representation of sets
ability to verify equality of specific combos. of ∪,∩
ability to verify containment of combos. of ∪,∩
complement, ', difference, -
- of two sets is a subset of first
- has no subsets in common with subsets of the second set
' has no elements in common with elements of the second set
' has no subsets in common with subsets of the set
A pair of sets is equal iff their complements are
' is idempotent
- is not assoc or commut
ability to see specific identities and inequalities with -,',∪,∩
the idea that ' presupposes a universal set
' is the same as that univ. set -
disjoint
two sets are disjoint when their ∩ is empty
the - is disjoint from its second argument
' is disjoint from its argument
two sets are disjoint iff all their subsets are disjoint
partition
a partition is a set of subsets of the set
each element of the set is in one member of the partition
each pair of members of the partition is disjoint
the partition induces the relation "is in the same class as"
this relation is an equivalence relation
each equivalence relation r breaks up a set into subsets of ≡ members
this division is a partition
reln. r induces partition p iff p induces r
a partition is interesting if its classes are
a partition is interesting if its induced reln. is
null set, NIL, ⊗4phi⊗*, {}, emptiness
the null set exists
the null set can be an element
the null set is a subset of each set
There exist efficient ways to prove a set is null (contradiction)
how to generate {} from each representation
singleton set, {{}}, (NIL), non-emptiness
how to generate a singleton in each repr.
how to make any object a singleton set
all the elements of a singleton are equal
if all the eles. of a set are equal, it is singleton
if one element is removed from it, is is empty
the only partition is the set containing itself
∩ with singleton is usually empty
∪ with singleton is usually adding in one element
- singleton usually removes that ele.
singleton - . is usually empty
the singleton is not the same as its element
doubleton, pair, non-identity of elements, ordered pair
how to generate in each set representation
not all eles. of pair are equal
only paritions are itself and as singletons
how each repr. admits an ordered pair
the relevance of ordered pair and commutativity
bigger-than-doubleton, more-than-two, several
call this idea big.
a set is big iff it is not {}, single, doubleton
a set is big iff the set of possible partitions is big
the set of subsets of a singleton is a pair
the set of subsets of a pair is big
the set of subsets of a big set is big
opaque way of enumerating subsets of a given set
opaque way of cyling thru all pairs of subsets of a pair of given sets
semi-opaque way of testing for 1-1 correspondence, bigger/smaller
a big set - a pair is never empty
a pair - a singleton is never big or empty
a singleton - empty is that singleton
the ∪ with big set is always big
the ∩ with non-big is never big
universal set, universe
the idea of a univ. set in each repr.
the reln. between univ., ', and -
all sets are subsets of this set
all eles. are eles. of this set
∪ is univ. if the sets are complementary
∪ is univ. iff one set contains the other's '
∩ is univ. iff one set is univ, other empty
' is univ. iff set is empty
- is univ. iff first is univ., second empty
univ. ∩ set is that set
univ ∪ set is univ.
univ - set is the complement of the set
set - univ. is empty
repeated unioning leads to univ.
repeated ∩ leads to {} muc easier than ∪ leads to univ.
do not operate with univ. sets as two args.
there is only one univ. set
infinity, finite, ∞
the universal set is infinite, unless explicitly specified
how to see that a set is infinite (in each repr.)
how to see that a set is finite
an infin. set - finite set is always infinite
infin. ∪ fin. is always infin.
infin ∩ fin is always finite
fin - infin is always fin (subset of orig. fin. set)
not all infin. sets are universal
Deduction -- much of this goes under problems-to-prove strategies
Truth, falsity, certainty
the logical universal set is a pair
statements are partitioned into two classes
Statements may be vacuously true
one type of problem is to determine the class of a prop.
when the class is not known, the prop. is uncertain
Definition, axiom, theorem, lemma
a definition is a convention for substitution
an entity should be defined if it is used often
an entity should be defined iff it is interesting
the truth of a definition is assumed true
the truth of an axiom is assumed true
an axiom is a relation between defined entitities
a theorem is the true result of a proof
a theorem is interesting if it is unexpected
a theorem is interesting if it is hard to prove
a theorem is the satisfaction of a top problem
a lemma is the solution of a low-level problem goal
a lemma is assumed true when proving a theorem, if it seems clear,
and then proved separately later
Proof, validity, unsatisfiability
a rule of inference is an operation which preserves truth of true prop.
an axiom is assumed to be "proved" (tho non-demonstratable formally)
there should exist an intu. justif. for an axiom
a rule of inference is assumed proved nondemonstrably
there should be an intu. justif. grasp of each such rule of inference
proven methods applied to proven state. yield proven statements
if the method and arg. are almost certain, so is the conclusion
proof by cases
reduce the pf. by replacing terms by their defns.
proof by indirect argument and reduc. ad absurdum
proof by deduction, directly
prop. is satisfied by all eles. of a set
if the satisfaction set is empty, the prop. is unsat.
if the sat. set is non-empty, the prop. is satisfiable
unsat. prop. is false
false prop. is unsat.
true prop. is satisfiable
a prop. is valid iff it is true
a prop. is valid iff all subsets of univ. set satisfy it
keep all thms. around for a while; destroy old ones if not reused
keep all pfs. around temporarily; destroy if not used as analogue
and, conjunction, ∧
min. truth value of tis args
simultaneity
or, disjunction, ⊗6∨⊗*
max. truth value of its args
choice, decisiion, deferral, alternative
not, negation, ¬
truth table for and, or, not
relation betw. and, or, not (specific cases only)
analogy to set operations ∩, ∪, '
complement truth value of its arguent
variable, constant
entity has name and value
value may be modifiable if needed, with certain constraints
variable can be assigned a value specifically
unassigned var. can make a prop. repr. ∞ props.
substitution, replacement
textual operation of replaement if functionally equivalent
instantiation of a variable to specialize a genearl prop
the replacement should serve some prupose
quantification, for all, ∀, existence, ∃, ¬∀, ¬∃
each var. has a domain of poss. values
thus one says for any <var> in <set>, <prop>
sometimes, only the existence is known, not the name
only the property of interst is known, not the name
identities involving ∀, ∃, ¬
implication, →, ¬→, equivalence, ↔, if, iff, only if
truth table interpr.
causality, entailment, and purely logical implic.
equiv. as double implication
intuition for →: set of states. satisfying left ⊂ those satis. right side
double causation: positive reinforcement
syntactic formats for expressing implication
reducing to a simpler yet equivalent entity
reduction by showing implication each way
equivalence if a complete circle of implications
expression in terms of ∧,⊗6∨⊗*,¬
scope, binding, free
how syn. one can specify what the domain of a var. is
when this changes
the dependence of ∃ var. on outer variables
a var. has same value within a given binding
subst. for var means replace all occurrences of it
constants must be identified syntactically
mathematical induction, recursion, well-ordering axiom
the equiv. "ideas" here
how one could actually go from induc. pf. to specific pf.
when to recognize an induction
base step: relevance, how to form it, idea of vacuous truth
how to form the hyp.
when it is better to strengthen/weaken the hyp.
rules of deductive inference, modus ponens and tollins
concept of truth tables
modus ponens, detachment, working forward
modus tollins, indirect proof, working backward
chaining
how to spot a relevant rule: pattern-matching
contradiction, reductio ad absurdum
logical justification for this unintuitive process
idea of pigeonholes, cases; here you show where it isn't
an entity exists in one and only one pigeonhole
cases
again, pigeonholes
relate to partitioning a set
if a statement is true about each class, it is valid
the adantage: the pf. may vary with the bin
Induction -- much is also relevant to prob-to-prove and prob-to-find strategies
plausibility, certainty, belief, betting, reliability
each statement has a probability weight attached to it
this number is a fn. of a list of justifications
if there are several alternate justifs., it is more plausible
if some consequences are verified, it is more plaus.
if an analogous prop. is verified, it is more plaus.
if the consequences of analogue are verif., it is slightly more plaus.
the converses of the above also hold
nothing is certain unless it has been (dis)proved
believe in those things with high enough prob.
this level should fluctuate, remaiing just high enough so that
no contradictions are believed in
the higher the prob., the higher the reliability
the amt. one bets should be prop. to the reliability
the interest increases as the odds do
conjecture, hypothesis, intuit, guess, assumption
push world, assert x, prove y, pop, assert x→y
if x seems probable and interesting, then try to prove it
the less sure x is, the less effort is spent on its ramifications
if a hyp. turns out wrong, reexamine its justif. routines
an assump. from the user need not be heavily justified
probability routines for handling derived statements
should be datachable module
Zadeh: p(∧) is min, p(⊗6∨⊗*) is max, p(¬) is 1-.
Hintikka's formulae (λ, α)
Carnap's formulas (λ)
p=1 iff both the start and the methods are certain
p=0 iff both start is false and method is false-preserving
if ∃ several alternative plaus. justifs., p is higher
don't update p value unless you have to
update p values of contradictory props.
update p values of new props
maybe update p value if it is a reason for a new prop
empiricism, experiment, random sampling, statistics
true ideas can be verified in all experiments
false ideas may only have a single exceptional case
nature is fair, uniform, nice, regular
more plaus. the more cases verified
more plaus. the more diff. types of cases verified
distinguished domain eles. are good cases to check
random domain eles. are good to check
large, hard, known-boundary cases are good type to check
if a consequence is unintuitive, check it instead
if it is intuitive, check it outside range of intuition
central tendency (mean, mode, median)
standard deviation, normal distribution
other distributions (binomial, Poisson, flat, bimodal)
statistical formulae for significance of hypothesis
what it means to be a generalization, a specialization
a gen. contains this concept
one can gen. by removing some constraint
one can generalize by replacing a constant by a variable
if the gen. is more regular it might be easier to prove
what it means to be an analogy, a model
to spec., add some constraint
if well-chosen, this constraint can make spec. easy to prove
from the spec., one can then try to prove this concept
to spec., replace var. by some special constant value
a spec. is included in this concept, but not vice versa ususally
analogy is a correspondnece betw. properties of 2 idas
the corr. should be natural, reasonable, clear intuitively
if the analogy is weak, examine the corr. and try to strenghten
if ana. is partial, see if pairs of remaining features match
if strong ana., usever obj. is best suited (2 aspects of 1 idea)
Operation
Relation
view as pair of intu. sets, with arrows from eles. in one to eles. of the other
The reln. is that set of arrows
Consider set of all poss. arrows; subsets of this are all the relns.
view as a temporal procedure, activity
view as a subset of ordered pairs
view as a subset of cross-product of sets in general
you can ⊗4carry out⊗* this thing
to do this, some things must be made true beforehand
some things will be true after; what are the effects?
when do you want to do this?
why do this? why not some sim. thing?
what are some gen/spec?
how to specialize/generalize a relation
function
uniqueness, singleton, single-valued
all facts about relns(because they are more general)
domain, range, image
what can this operate on, what props. must be satisfied?
what do yo know about the result, what props will it satisfy?
each of these properties forms a set, called dom. and range
the op. is said to be from dom. to range
X{A↓i} view A↓j as rage, X of others as domain
inverse, preimage
think of reversng order in cross product
think of reversing order of ordered pairs
think of running time backward for temporal op.
think of finding the value which maps into a given one
think of undoing an activity, a process
preimage of ele. is all eles. which map into it
preimage of set is union of all ele.'s preimages
preim. if set is all eles. which map into an ele. of set
preim. of range should be entire domain
onto, surjection
image of set is all eles. it maps into
onto means image of domain is entire range
onto means ∀ range ele., ∃ preimage ele. in domain
means that the inverse relation is defined on whole range
1-1, injection
if inverse (wherever it is defined) is a function
no two eles. map into same unless ⊗4they⊗* are same
on graph, no horiz. line intersects two pts. in reln.
1-1 correspondence, bijection
injec and surjec
injec each way
surjec each way
match eles. one to one; e.g., remove one from each set
inverse is also a bijec.
composition, associativity
if f1, f2 are relns, with domain of f2 a subset of f1 range
apply f1, then apply f2 to result
write F2(F1(x)), (F2 (F1 x)), (F2 F1 x), F2oF1 (x)
assoc: For any relns, F1o(F2oF3) ≡ (F1oF2)oF3
relns are equal when they are the same set of pairs
uniqueness
a fn or obj is unique only wrt conditions c
if x,y both satisfy c, then uniqueness means x=y
once one is found, stop because there aren't any more
extension, restriction
if the dom. is a subset of a nice dom. D, try to apply to all D
if the dom. contains D, see if new props. when only apply to D
if range contains nice set R, see if nice if restricted to map to R
if range is contained in R, OK to say that range is R already
often the domain can be changed by changing the contraints
the range will vary as the domain varies
consider the inverse fn.
fixed point
if range intesects domain, possibility that x maps to itself
if so, then x maps to itelf under all +-powers of fn.
identity function
one fn. is to map each ele. to itself
here the domain and range are identical
also ok if range contains the domain as a subset
the inverse fn. is defined on the domain only, though
in this case it, too, is the identity fn.
all +-powers of fn are the identity
repeated application of a function
if dom. containsrange, one can keep reapplying fn.
reapply means keep forming composition, higher powers
if domain and range intersect, repeat until in difference
often dom. will be power of range; this is interesting
in that case, choose n eles. first time, n-1 from then on
n that case, consider using disting. eles. later on
symmetry, reflexivity, transitiviy, equivalence, partition
binary fn. is one from SxS into S. call it f.
f is symm. means that arg. is unordered pair
f is symm. means that rotate graph 90↑o is invariant
binary reln. is from S to S. call it g.
g is symm. means g = g↑-↑1
g is reflexive means it contains all pairs (x,x)
g is reflex. means one place x can go is itself
g is reflex. iff all +- powers of g are
g is reflex. iff any +- power is
g is transitive if <standard>
g is tran. means that <picture composition of graphs>
f is commut. iff it is symm.
f is assoc. if it takes bag as arg
f is assoc. iff it is the compos. of assoc. fns.
an equiv. reln is reflex,trnasitive,syymmetirc
such relns divide set into disjoint classes
pairing
a fn is assoc with it s value, they are paired together
this is one view of a fn, as a set of ordered pairs
unordered pairs iff f equals its own inverse
true for relns, not just fns, here
Procedure, sequence, seriation, program
temporal order, the flow of time, clock
advancing variable of state
causal arrow i often assoc. and disc. by time precedence
often one activity must follow or precede another
a seq. of steps is to be executed in order
often the result of one step will be needed for the next
if not, the ordering is only partial, only some < are needed
Parallel, simultaneous
if no < are needed, do in any order
in none allowed, do a little of each in turn
start and finish all about the same time as each other
Ordering, partial and total, ≤, ≥, <, >, =, trichotomy
if can be simult. or precede, write ≤
≤ is negation of sucession, >
disting. between when one can pre-succ., and when it must do so.
two events are simult or else one preceds the other
Structure
tree, binary tree
node, argument, element, primitive unit
link, connection, ordering, relation, property
traversal, pre-post-ordering, covering, search
tuple (associativity of functions), list, vector
if fn is assoc, SxS to S
only the relative order of the arguments is relevant
if f(a,f-vector), then cons(a, f-vector) (after f)
if f(f-vector, a) then insert a at rear of f-vector
bag (commutativity and associativity)
if f: SxS→S is assoc and commut.
the order of eles. in the tuple can be changed
duplicate eles. cannot in general be removed, though
use the order for some other reason (effic., e.g.)
set, class, collection
if f:SxS→S is assoc, commut, and f(x,f(x))=f(x)
duplicate els. in the bag can be removed
by ana: use the no. of occurrences for effic. considerations
trivial cases of each structure
singleton, doubleton, empty sets; big sets
iden. fn., constant fn, step fn.
set-theoretic fns. all take sets as eles.
projection fns. require trees
append of lists of x's takes bag of such lists
regularity, order, form, arrangement
economy of description means regularity exists
aesthetic desc (ana. to known descs. elsewhere)
each part of desc. is organized regularly
the parts are related regularly
Conservation
of inertia; frame problem
if no explicit evidence, things continue once begun
some activities require constant supportive (friction) action
the truth of pros. obeys this inertia law as well (frame prob)
invariance
a part of each BEING
what can be done and have no effect on this one
what does this have no effect on
if shorter, store the negation of these
(in)elasticity, fluidity, rigidity, plasticity
reaction to stress, force
compressable or not
fluid or stiff
idea of maniipulable by a slow, continuous effort
Control
what a stragegy means, what a meta*-strategy means
choice, decision
goal, object, end, purpose
problem, solution, search, task
Handles (how it can be accessed)
existence can be proven
constructive proof
efficient algorithm for construction
built into the language, pointer
Strategies ⊗6(for each, supply hints as to how to pick likely candidates, in case no other good reason is known)⊗*
General
Examine partial BEINGS; use part-specific info to aid in completing them
Find analogies: find regularity among concepts
Identify the parts of the object, and relns. involving it.
Expend energy to fill in some addl. parts of chosen B.
Try to determine which classes of things have similar kinds of parts/relns,
If too huge, then this B. loses interest
Search through them to find those whose parts' values are similar,
If slightly int. one is found, try to fill out some of its parts
If interesting, propose as a new analogy contruct (as a B.)
How to select candidates for drawing ana. with:
Lin. combo. of evaluation vector components (use, int, genl)
Lin. combo of lengths of parts filled in already for B.
Measure of how many parts, and varied, are filled in
If unaccep., record why; if another is sim. rejected, they may be ana.
Extend existing analogies
Conjecture that each reln. involving one has an analogue with the other
If parts/relns A,B are often connected, try to connect their values here
Consider analogies between genral/specializations of each concept
Refine existing analogies
If all you know is that 2 Bs. are related somehow, this deserves refinement
Find parts of one having no analogue in the other
Find parts which are connected but whose values aren't
Find regularity within this concept itself
Identify the parts/relns of this concept
Some of ⊗4these⊗* may be related, similar
Some pattern may recur throughout the values of the parts, types of relns
Explore regularity within a concept
Conjecture that relns involving one part hold analogously for the similar part
Conjecture that relns. holding for sim. parts are themselves related
Can some more efficient representation be found to avoid this duplication?
Contradiction: what it means, how to resolve it
⊗6This is of course dependent upon the mechanism and representation for belief⊗*
If the pair A,B of concepts lead to belief in a known false statement,
then re-examine and revise the reasons for believing A and B.
Choice: algorithms, hints for selection, decision-making
Resources have limited throughput; goals must guide attention
Thus choices must be made, based on the values of the researcher.
Prefer the most interesting candidates (exponential curve)
Prefer the safest candidates (peaked distribution)
Recall analogous choices, the predominant factor, and evaluate the result
Use this to in-/de-crement the importance of this factor in the choice algorithm
A first pass alg. might be w↓1e↑I * w↓2sin(S), where
"I" is the interest, "S" the normalized safety
Do not simply maxi-minimize: bonus for several promising branches
Better assimilate each concept
Identify (from scratch, or improve the handle)
Tie to other concepts (by deduction, analogy, guess, intuition)
Improve intutive grasp of this concept.
Concentrate on interesting concepts mainly
Halt when interest level of results (averaged) falls too low
Evaluate concepts
How interesting
How safe, sure, complete
How valuable are its analogues
Any valuable consequences/uses
How intuitive
How efficiently represented, what type of handle
Evaluate its parts, combine results
Make any part a new BEING if it is much more intersting than whole
When examining any new entity (operator, object, construct, concept)
Identify
Get a name for it, alternatives, how it might be later referenced
Ensure that this is in fact new, not an old concept
Assimilate
If a pair of new, specific, non-random entities are generated in a row,
Then high interest in tieing them with known specific relations
Try to grasp this intuitively
Try to tie this in to other, existing concepts
Use the partial results of each of these to aid in the other!
Boundary: get limits of this concept/definition
Empirically, what do the limits seem to be
Intuitively, what do the limits seem to be
Can any formal boundary be described
Try to reconcile all these opinions of the boundary
If all but one version is similar, try hard to bring the dissenter to agree
Extension/restrictions
Is the boundary close (⊂,⊃) to a much more interesting set?
If so, can it be so restricted/extended?
Does the concept become more interesting? Use the special props. of new boundary.
If not, perhaps the original idea of the boundary was wrong; recheck.
If so, should the original concept be kept around at all?
Extension often requires weakening the concept, restriction strengthening
Handle: get the most concrete, efficient handle possible on this
Character
If this belongs to a class with a known ≡ reln, see which ≡ class it falls into
Combination
What are the similar entities
How can this be combined with similar entities
What are the more general(spec) concepts, and how do they differ
Is there a more economical repr., in terms of some close concept + a difference
Does this contradict anything (hint: consider intuition first)
Examples
simple, trivial, involving already-distinguished simple sub-parts
sophistocated, sufficient for empirical verification of future conjecs.
boundary, near miss; may be gotten only from a large random collec.
typical, representative, suitable for intuitive prediction
When examining a new operation "f"
Definite: get names for function, its domain and range
Calculation: get algorithm for computing f
Character: see if it is a function or only a relation
Image: what subset of range R does the domain D map onto
Extension: can D be extended so f is ONTO R, or onto Q⊃R
Restriction: can R be restricted so f is ONTO R
can D be restricted so f is 1-1 into R
Closure: can D be made to contain R or R↑2 or R↑3 or...
If closure holds: what are the fixed points of f,
consider powers of f, is there an identity
(left, right, both), do special elements of
D map into other special elements, do special
subsets map into special subsets.
Consider compositions of f with itself as a
tree; now what tree manipulations leave the
value of the tree invariant.
Composition: consider f*g, where g maps into a subset of D,
and h*f, where h maps from a superset of R.
Treat these as new operations, but (to avoid
infinite regress from this rule) reduce the
level of interest.
Similarity: search for other functions g which equal f on
some part of D. Say g maps from E to F.
If D is close to ExH for some H, try to find
when f(e,h) = g(e), for special h⊗6ε⊗*H.
If E is close to DxH for some H, try to find
when f(d) = g(d,h), for special h⊗6ε⊗*H.
Examples: Find some examples of this operation. Try for
representative, simple, and hard examples.
Try to find boundary cases, where the function
just barely applies/ doesn't apply
Intuit: Try to construct an intuitive representation for f.
Identify: Initialize a list of ways that f might be referred
to in the future, both directly and by desire.
When examining a non-procedural object (set, class, concept)
Containment
Interesting subsets and supersets
Identity
name, interesting properties, distinguishing features; see above
Operations
What can/can't be done to it, why, how to alter this
Is this the natural dom/range for any operators?
If so, how do they affect special subsets of this set?
When examining a semi-procedural problem to prove (theorem, conjecture)
Worth: what effort should be expended on its pf/disproof
Intuition
How can this be assimilated, understood intuitively
How is this intuitively justified (manipulate intuitions)
Does this indicate a proof, counterexample, type of proof,...
Definiteness
Can a def., formal version of this be stated
Collect the names of the specific, needed but blank parts
Each such absence lowers int. and raises cost
If too costly, low int, store pointer to conjec in blank parts
The conjec. maintains set of still-blank definite parts, evidence collected
Substitute defns for terms in conjecture iff ∃ good methods for defns' terms
Tie-ins
entailment, causality with similar subject matter
equivalent restatements of this proposition
Boundary
What are the most likely counter-examples (and patches)
Can any of the hypothesis be relaxed? Why not (intuition + formal)
Can the conclusion be strengthened? Why not? (intui + formal)
Consider the converse, both intutitively and formally
If fail: if x is intuitive but still resists proof
Perhaps x is an axiom, simply to be asserted (if v. useful; ask user)
Perhaps some different or not-yet-known pf. technique is needed
Perhaps some diff., unexpected, or not-known knowl. is needed
Perhaps it is false, and intuition is misleading and should be modified
When examining a semi-procedural problem to find
Identify the parts
given (fixed, known)
unknown (goal)
Evalutate
why this is interesting
should be difficult yet doable
usable later (interesting consequences)
Pull out the relevant facts
use analogy, patterns, relevant relations
Analogy
Find similar tasks (sim. problem, some features in common)
Can the result be useful
Can the method be useful
Unify the intuitive and formal reprs. contributions
What is the idea/form of the soln?
Prob→intuit→soln. with intuitive obj./relns.→definite obj/relns(almost def. soln)
Should be able to reverse the arrows on the above chain
Meta-strategies
Below, α means ⊗4increases with increasing⊗* (proportionality), and
α↑-↑1 means ⊗4decreases with increasing⊗* (inversely proportional).
Completeness of an analogy α safety of using it for prediction
Completeness of an analogy α↑-↑1 how interesting it is
How expected a relationship is α↑-↑1 how interesting it is
How intuitive a conjec/relationship is α↑-↑1 how interesting it is
How intuitive a conjec/relationship is α how certain/safe it is
How superficial something is α how intuitive it is
How superficial something is α how certain it is
How superficial something is α↑-↑1 how interesting it is
Also included here should be algorithms for applying these rules
to choosing the best strategies, as a function of the situation.
Crude estimate of interest level is the interest component of the eval part
Modify this estimate in close cases using the above relations
Generally, choose the most specific strategies possible
If the estimated value of applying one of these falls too low, try a more general one
Rework the current B. slightly, if that enables a much more specific strategy to be used
When examining a reln, treat as a problem to prove, (hint: intutiion often helps)
The basic idea is to choose a part and a B, and fill in that part of that B.
Choose a part on the basis of int., understanding of the usefulness of that value
Locate specific concepts which partially instantiate general strategies
The more specific new strategies are associated with the specific info. used
Once chosen, use the strategies on the most promising specific information
If a strat. falters: Collect the names of the specific, needed but blank parts
Each such absence lowers int. and raises cost, and may cause switch to new strategy
If too costly, low int, store pointer to partial results in blank parts
The partial results maintain set of still-blank needed parts
Meta-meta-strategies
Competing goals: On the one hand, desire to maximize certainty,
safety, complete analogies, advance the level of intuition.
On the other hand, desire to maximize interestingness, find poss. and poten. interesting ana.
find unexpected, nonsuperficial, and unintuitive relationships.
If an entity is used frequently, it should be made efficient.
Conversely, try to use efficient entities over nearly
equivalent (w.r.t. given purpose) but inefficient ones.
If an entity is believed but powerful (unintuitive), its use is
dangerous but probably very interesting.
Resolve choices in favor of aesthetic superiority
Also included here should be specific algorithms for applying these
rules to choosing the relevant meta-strategies.
Meta-meta-meta-strategies
Maximize desired effects
In this case, prefer hi interest over hi safety in meta↑2strategies
Minimize costs, conserve resources
In this case, prefer safety to interest i meta↑2strategies
Locate the most inefficient, highest-usage entity, and improve or replace it
Meta-meta-meta-meta-strategies
There is no "choice" here; all of these are eternal and implicit:
Maximize net behavior
Generally prefer the "desired effects" meta↑3strategies
If time/space become a problem, worry about conservation until this relaxes
.NEXT PAGE
.FILL
⊗23. REPRESENTATION⊗*
Much of this was transferred to the thrid sketch (qv).
⊗5Level 2⊗*
DEFINITE KNOWLEDGE
A proposed set of BEING parts follows, for those types not carried over into
the nsext ketch.
Part of the driving force of the system is the urge to ⊗4complete⊗*
each BEING.
.NOFILL
⊗4Possible parts of a META-STRATEGY BEING:⊗*
NAME identification
(NOT)(QUICK)IDEN recognize relevance
FAMILY AFFECTED what family of specific information BEINGs is affected
PARTS AFFECTED what strategies (parts) are affected
INDIVIDUALS AFFECTED specific BEINGs in the affected family, listed only by description
ORDERING if a new Metastrategy BEING is created, what order to fill in parts
IF FAIL what to do if the strategies report failure
IF SUCCEED what to do if strategies succeed in filling in desired parts
IF INTERRUPT when to ignore, when to accept, when unsure: who to ask
VALUE how costly this is, how well-focussed, how productive
GENERALIZATIONS what MS BEINGs are similar but slightly more general
SPECIALIZATIONS what MS B's are more specific cases of the current one
USE what situations is this most effective in
WHY justify making this a new separate BEING
IMAGE analogic interpretations, intution. Rarely filled in here.
BOUNDARY what causes the sit. to fluctuate s.t. this B. is/is not relevant
⊗4Possible parts of a META-META-STRATEGY BEING:⊗*
NAME identification
(NOT)(QUICK)IDEN recognize relevance
INDIVIDUALS AFFECTED specific MS BEINGs affected, listed only by description
IF FAIL what to do if the strategies report failure and MS can't cope
IF SUCCEED what to do if metastrategies succeed
IF INTERRUPT when to ignore, when to accept, when unsure: who to ask
VALUE how costly this is, how well-focussed, how productive
GENERALIZATIONS what MMS BEINGs are similar but slightly more general
SPECIALIZATIONS what MMS B's are more specific cases of the current one
USE what situations is this most effective in
BOUNDARY what causes the sit. to fluctuate s.t. this B. is/is not relevant
.FILL
Common knowledge should in some cases be factored out. Possibilities:
(i) always ask a specific BEING, who sometimes queries a more general
one if some knowledge is missing; (ii) always query the most general
BEING relevant, who then asks some specific ones (This sounds bad);
(iii) ask all the BEINGS pseudo-simultaneously, and examine the
responders (this sounds too costly.)
At some level, probably meta↑3strategies and above, a small collection of rules
will be all that is required. One might view this change as gradual, as the
number of BEING parts decreases with the level increasing. By the foorth level,
what is left is truly more of a structured rule than a BEING.
A scheme for organizing the pointer systems for RULES now follows.
Each rule will have several types of pointers, to indicate relevant
rules. One set might be as follows:
.NOFILL
ABSOLUTE The rules pointed to here should definitely be examined.
SUCCESS If this rule succeeds, then look at these anyway.
FAILURE If this rule fails, by a little, then look at these. (More descriptive, perhaps).
EXTEND If a more comprehensive result is desired
CONTRACT If a more restricted, simpler result is desired.
COST What is this rule's expense of execution? Its chance of success?
Point to cheaper rules/functions; point to costlier rules/BEINGS?
INTUITION Point to abstract intuitive rules relevant to this rule.
CONCRETE Point to less abstract rules which are related to this one.
.FILL
Notice that the rule parts are simpler, fewer, and more uniform than the set
of BEING parts. A simple pool of unstructured rules might be all that is needed
(situation action productions).
.NEXT PAGE
⊗24. COMMUNICATION⊗*
⊗5Standard Math Notation⊗*
.NOFILL
IMPLICATION
IF ... THEN ...
IMPLIES
IFF
IF
ONLY IF
IS IMPLIED BY
THEREFORE
THUS
SUPPOSE ... THEN
LET ... THEN
THEN
SO
HENCE
IN ORDER TO...
IT SUFFICES THAT
NECESSITY
SUFFICIENCE
→
←
↔
WHENEVER
WHEN
SPECIFICATION
SUCH THAT
SATISFYING
WITH
WHERE
SOME
THE
A/AN
ALL
EVERY
NO ... IN
∀
∃
FIXED
VARIABLE
ANY
EACH
MOST
THERE EXISTS
WHICH
THAT
THIS
OTHER
COMBINATION
AND
OR
∧
⊗6∨⊗*
NOT
¬
ALSO
BUT
OPERATION
FUNCTION
RELATION
PREDICATE
FN/FCN/FUNC
f/g/h
DO
APPLY
COMPUTE
OPERATE
PRODUCE
ACCORDING
CORRESPOND
ALGORITHM
<silent imperative>
COMPOSITION
o
MAP
TAKE
SEND
PULL
IMAGE
RANGE
DOMAIN
f:D→R
PREIMAGE
INVERSE
UNDEFINED
DEFINED
f(a,b,c)
f↑-↑1(x)
f↑-↑1
CLOSED
PARTIAL
TOTAL
DEFINITION
DEFINE
CALL
=df
NOTATION FOR ...
REFER TO...
NAME
KNOWN RELATIONS
EQUALITY
=
IS/ARE
INEQUALITY
GREATER
LESS
SUBSET
⊂
⊃
CONTAINS
INCLUDES
MORE
INTERSECTS
∩
UNION
∪
APPEND
BETWEEN
INSIDE
OUTSIDE
INCLUSION
EXACTLY
COMPLEMENT
SETDIFFERENCE
+,-,x for sets
CONS
CAR
CDR
FIRST
LAST
ALL BUT
JOIN
PREVIOUS
PRECEDE
SUCCEED
FOLLOWING
NEXT
NEAR
FAR
CLOSE
ANALOGOUS
ENTITIES
ATOM
ELEMENT
CONSTANT
VARIABLE
SET
TUPLE
BAG
MEMBER
⊗6ε⊗*
THING
ENTITY
OBJECT
IDENTIFIER
NAME
LABEL
VALUE
⊗5Fixed Formats for Quasi-English Meta-Comments, Questions, Hints⊗*
ACTIVITIES
DO...
CONSIDER...
USE
LOOP
REPORT
DISTINGUISH... AND/FROM ...
EXPLAIN
DISCUSS
GET
RESTRICTED CONCEPTS
ELLIPSIS
ETC.
AND SO ON
...
SIMILARLY
ANALOGY
SIMPLIFY
REDUCE
FAILURE
SUCCESS
THINK
CONCENTRATE
CONSIDER
ATTEND
ASSUME
SOLVE
PROVE
pronouns
SEE
HYPOTHESIS
PROBLEM
SOLUTION
INVESTIGATE
DISCOVER
UNDERSTAND
TIME AND SPACE REFERENCES
EARLIER
LATER
BEFORE
AFTER
THEN
NOW
NEVER
ALWAYS
HERE
THERE
UNDER
ANYWHERE
NOWHERE
INDEFINITES
SHOULD
WOULD
COULD
MIGHT
POSSIBLE
PROBABLE
PLAUSIBLE
BEAUTY
POTENTIAL
CAN
forms of TO BE
OUGHT
CONFUSION
DEFINITE/INDEFINITE
CERTAIN/UNCERTAIN
TRANSLATE
DIFFICULTY
PLEASURE
SO
UNIQUE
EXISTENCE
QUESTIONS
WHAT x
WHY/WHY NOT x
HOW
WHEN
.FILL
⊗5Fixed Languages for Intuitive Communication⊗*
These have not yet been examined at this level of detail.
.NEXT PAGE
⊗25.EXAMPLES⊗*
⊗5Example 1: Contemplation; forming links, intuitive conjectures⊗*
.FILL
Following is the protocol of the first attempt to exercise the given
knowledge. The system was to be starting for the first time, at the
most removed level of strategies (meta-meta-meta-meta strategies being
fixed).
.NOFILL
Meta-meta-meta strategy: To maximize desired effects (since there are
no costs at present)
Meta-meta strategy: To find potential analogies and maximize interest
(in view of the meta-meta-meta strategy chosen)
Meta strategy: To find new, incomplete analogies (since they are more
interesting)
Strategy: Find analogies (general strategies are considered, for lack of
something in particular to concentrate on, and this one is chosen
because the rest are currently inapplicable)
(1) How to select candidate objects for the analogy: prefer intuition
in general; try for one with many completed parts; select a
relation (relations are more complex and interesting)
(2) Identify the parts of the object (i.e. Relations)
intuition: view as the set of all arrows from elements of one set to
elements of another
specialization
(3) Try to fill out additional parts of the Relations being, namely Examples:
(i) Quick: specific relations and functions: ⊗6ε⊗* ∪ ∩ = ⊂ - ' ∧ ⊗6∨⊗* ¬
(ii) Consider intuition part, make it concrete
(a) consider 0 as one set. Consider the intuition of
a relation (set of arrows between two sets' elements).
There can't be any arrows to or from 0. So the only
relation to or from 0 is the 0 relation.
This conjecture has a relatively high interest, so the current state of activity
is suspended and new goals are chosen:
Meta strategy: Examine an unexpected (hence interesting) conjecture (i.e. look
under "When examining a semi-procedural problem to prove")
Strategy: Problem to prove
Intuitive justification: {...}---------→ {}. {} --------→{...}
There is no place for the arrow to point or stem from in order to form
a relation one of whose arguments is 0. No arrow head or tail can be tied
to an element of 0, because there are no elements in 0.
Definiteness: There is currently no definite part of the Relations being
filled in. Hence interest drops, cost rises, this activity (proving the
conjecture) is stored (in the definition part of the Relation being).
Meta strategy: Restored to: Find analogies
Strategy: Restored to
(3) Filling out Example part of the Relation being
(b) Simple examples: plug in singletons as the two sets being
related. Experiment reveals two relations between them:
0 and elt1 --------→ elt2.
Here another conjecture is made, as above, that between two singleton sets
there are exactly two relations. The intuitive justification is found, but as
before, there are no definitions available now, so proof activity cannot
procede. The original state is again restored.
(c) Harder example: a singleton is related to a pair set. Many
possible relations are found.
(d) Pair to Singleton relation. As many relations as singleton
to pair.
(e) Pair to Pair relation considered. More relations found than
between singleton and pair.
(f) Sophisticated examples: none known
(g) Boundary examples: none known
(h) Typical examples: generate a few random sets A, B, C...compute
all relations from each to each. One set is big, and after a
while system demon tags FIND-ALL-RELATIONS as a combinatorially
explosive operation.
A conjecture is made that there is a 1:1 correspondence between the relations
between X and Y and those between Y and X. Interrupt to a new strategy:
Strategy: Find all known relations among newly generated specific entities.
Conjecture to Prove.
Intuitive justification: reverse the arrows between the two sets. Support
comes from the conjectures about 0 and singletons.
.
.
.
continues in this way
Eventually, there are enough conjectures on Relation's definition part, so that
the prevailing goals are interrupted again to become:
Meta strategy: Propose to fill in the definition part of relation
(not trivial at this point...)
Strategy: Fill in this part using intuition to get algorithm for FIND-ALL-RELATIONS
Algorithm: sets → intuitive representations → all arrows drawn → all relations
.SKIP TO COLUMN 1
⊗5Example 2: Discovering and developing a family of analogies⊗*
Meta-meta strategy: to maximize interest
Meta strategy: Partially complete a very incomplete analogy: System is given
that ∪ (union) and ⊗6∨⊗* (disjunction) are related in some way.
Strategy: Refine existing analogy
(1) Fill out parts of OR being
(a) already has intuition: sticks of length 0 ≤ x ≤ 1 represents
the arguments of OR. Always choose the bigger stick, to
evaluate OR of two arguments.
(b) (already has Results and Domain/Range parts)
(c) fill in Examples part
Work with extreme simplest stick lengths, 0 and 1 = s0 and s1
Experiment gives rise to these conjectures:
s0 ⊗6∨⊗* s0 = s0
s1 ⊗6∨⊗* s1 = s1
s1 ⊗6∨⊗* s0 = s1
s0 ⊗6∨⊗* s1 = s1
Then choose a more representative pair of stick lengths A, B
with A > B:
A ⊗6∨⊗* A = A
A ⊗6∨⊗* B = A
B ⊗6∨⊗* A = A
B ⊗6∨⊗* B = B
(d) Calculation part: already knows: for two statements, find the
two sticks that intuitively represent them, hold them up to
each other, pick the bigger one, return the corresponding
statement
(2) Fill in parts of UNION being
(3) note:
F ⊗6∨⊗* X = X
F ⊗6∨⊗* F = F
F ⊗6∨⊗* X = X ⊗6∨⊗* F
T ⊗6∨⊗* X = T
T ⊗6∨⊗* T = T
T ⊗6∨⊗* X = X ⊗6∨⊗* T
(4) Possible analogous parts: ⊗6∨⊗* to ∪ implies F corresponds to 0, T to Universe
⊗6∨⊗* to ∩ implies F corresponds to Universe, T to 0
∧ to ∪ implies F corresponds to Universe, T tp 0
∧ to ∩ implies F corresponds to 0, T to Universe
(5) whole network of analogies can be respesented schematically as:
.BEGIN SELECT 8 NOFILL PREFACE 0 MILLS TURN OFF "↑↓"
∨ ααααααααααααααα→ ⊗6∪⊗*
↑ ↑
~ ~
~ ~
~ ~
↓ ↓
∧ ααααααααααααααα→ ⊗6∩⊗*
.END
The horizontal lines are the relation α, connecting logic and set theory.
The diagonal lines (not drawn) are β, connecting the 2 domains in a diff. way.
The left vertical line is the relationship of being in the domain of logic.
The right vertical line menas "in the domain of set theory".
So, (i) α, β are very interesting analogies
(ii) there exist other analogies: αβ↑-↑1 is a relation in Logic
analogous to the relation βα↑-↑1, also in Logic, etc.
(iii) consider extending α and β to other objects from Set theory
and Logic. Is αβ↑-↑1 always equal to βα↑-↑1 ?
.SKIP TO COLUMN 1
⊗5Example 3: Formally Investigating an intuitively believed conjecture⊗*
Note: It is difficult to find hard proofs at this low level.
(1) Conjecture: The only relation from 0 to any set X is 0.
Strategy: Conjecture to prove
Intuitive Justification: Cannot seem to find any place for the arrow to
come from (i.e. can't draw arrow because can't choose an element from
the domain because there aren't any)
Definite: A relation between A and B is a subset of A X B.
A X B is the set of all ordered pairs <a,b> such that a ⊗6ε⊗* A and b ⊗6ε⊗* B
An ordered pair <a,b> is the set {{a},{a,b}}.
Strategy: To prove Any α is β, consider any α, show it's β.
Consider any relation R: 0 → X. Show it is 0.
Show all subsets of 0 X X are 0.
Intuition: All subsets of a set are empty iff the set is empty. (Becomes a
lemma.)
Must show 0 X X = 0 for all X.
This is intuitive. (Becomes a lemma.) Done.
Strategy: To prove p iff q, prove p implies q and q implies p. To prove
p implies q, assume p and the negation of q, and derive a contradiction.
Now must prove two lemmas, by contradiction:
(1) Say X is not empty but all its subsets are. If X is not empty,
there is some x ⊗6ε⊗* X. If x ⊗6ε⊗* X then {x} ⊂ X. Contradiction.
Say X is empty but is has a non-empty subset Y. If Y is non-
empty, there is some y ⊗6ε⊗* Y. By definition, y ⊗6ε⊗* X. Contradiction.
(2) 0 X X is the set of all ordered pairs (a, b) such that a ⊗6ε⊗* 0 and
b ⊗6ε⊗* X. Suppose 0 X X is non-empty. Then there is such an ordered
pair. Then there is an a such that a ⊗6ε⊗* 0. Contradiction.
Popping up, we discover that (1) is now proved.
Try to prove the converse of (1).
Analogy with last proof (this will actually work) OR
Establish the easy results in the following sequence:
if R relates A to B, then R↑-↑1 relates B to A
if R is the empty relation, then so is R↑-↑1
if R relates any set X to 0, then R↑-↑1 relates 0 to X
but by the last theorem, R↑-↑1 must be the empty relation.
So R must be the empty relation. So the converse is proved.
.FILL